This invention relates generally to systems for image processing, and, more particularly, relates to apparatus and methods for visually enhanced depiction of multivalued grey tone images on binary display devices or print media.
Digital halftoning methods and apparatus have gained considerable attention in recent years. These techniques are widely used for rendering "continuous tone" or multi-valued grey tone images on binary display devices or printers. When applied to a continuous tone image, halftoning generates a binary image in which the average density locally simulates that of the continuous tone image. Digital halftoning is frequently utilized in the desktop publishing field, in connection with computers that prepare images for printing. Due to the limited resolution of conventional laser printers--typically 300 dots per inch--the visual quality of laser-printed halftone images is dependent upon the method used to process the image.
In addition to printing, halftone images are used to display visual information on computer binary monitors and other bi-level displays. Such display devices are discussed in Jarvis et al, "A Survey of Techniques for the Display of Continuous Tone Pictures On Bilevel Displays," Computer Graphics and Image Processing, Vol. 5, pp. 13-40, 1976. The advent of miniature, head-mounted binary display devices of moderate resolution has also generated increased interest in halftoning methods and apparatus. See Peli, "Visual Issues in the Use of Head Mounted Display," Proceedings of the SPIE, Vol. 1099, Visual Communication and Image Processing IV, 1989).
Additionally, the continuing development of telecopiers, picture phones and other systems involving high-speed transmission of visual images over limited bandwidth communication channels has augmented the need for enhanced halftone imaging. Halftoning techniques provide data compaction by generating a compressed form of visual information suitable for efficient transmission over limited capacity channels. This application of halftoning is discussed in Roetling, "Quality Measures in Digital Halftones", Optical Soc. of Am., Washington, D.C., Topical Meeting on Applied Vision, 1989, Technical Digest Series, Vol. 16, pp. 59-62; and Anastassiou et al., "Digital Image Halftoning Using Neural Networks," SPIE Visual Communications and Image Processing, Vol. 1001, pp. 1062-1068, 1988.
Conventional halftone methods impose a compromise between spatial resolution and dynamic range--i.e., the number of grey tones represented--and the necessity of maintaining visually pleasing image texture and perceived roughness. This compromise is discussed in Saghri et al., "Personal Computer Based Image Processing With Halftoning," Opt. Eng., Vol. 25, pp. 499-504, 1986; and Ulichney, "Dithering With Blue Noise," Proceedings of the IEEE, Vol. 76, No. 1, January 1988, pp. 56-79.
Visually acceptable output images can be obtained through conventional digital halftoning methods if extremely high resolution displays or printers are available. However, when commonly available, moderate-resolution printers or displays are employed, conventional methods produce output images with objectionable visual artifacts. These artifacts can result from limited dynamic range or limited spatial resolution in the output image.
Halftoning methods can be divided into four categories: (1) dithering techniques, (2) constrained average or edge emphasis techniques, (3) error diffusion or propagation techniques, and (4) adaptive methods. A review of the first three classes and a comparison of their performance is found in Jarvis et al., cited above.
Dither halftoning methods generate a binary image by comparing the original image value to a position dependent set of thresholds within a small repeated cell containing an N.times.N array of pixels. This technique is discussed in Hou, Digital Halftoning and Shading in Digital Document Processing, John Wiley & Sons, New York, 1983, pp. 83-115. The selection of the threshold values and the positions of the threshold values within the cell determines the type of dither technique. In particular, the position of the threshold values within a cell can be random or ordered, and the position of the dots within the ordered screen can be dispersed across the cell or clustered together.
In applications utilizing printers or other devices in which the fidelity of single dot reproduction is low, clustered dots and ordered screens produce better results than do dispersed dots and random screens. In clustered dot methods, diagonally oriented patterns are preferred because of the limited sensitivity of the human visual system (HVS) to diagonal patterns. This is discussed in Ulichney, Digital Halftoning, MIT Press, Cambridge, Mass., 1987.
Dispersed dots and ordered screens are preferred for use with devices having reliable dot reproduction, because dispersed dots provide increased spatial resolution at a given dynamic range of gray levels. One method of dispersing the dots is proposed in Bayer, "An Optimum Method for Two Level Rendition of Continuous-Tone Pictures," Proc. IEEE Int. Conf. on Communications, Conf. Rec., pp. 26-11, 26-15, 1973. The Bayer method alternates horizontal, vertical, or diagonal points at each gray step. A significant limitation of the Bayer method of dispersed-dot dithered halftoning, however, is the distinct visibility of certain textures that produce the appearance of false contours in some images.
Constrained average methods typically provide greater apparent resolution than that afforded by dither techniques, with a consequent reduction in aliasing. These methods are discussed in Roetling, "Halftone Method with Edge Enhancement and Moire / Suppression," JOSA, Vol. 66, pp. 985-989, 1976; and in Jarvis et al., "A New Technique for Displaying Continuous Tone Images on a Bilevel Display", IEEE Transactions on Communications, August 1976, pp. 891-898. Constrained average techniques enhance the appearance of edges by calculating local averages and adjusting the dither threshold value locally. The effect is equivalent to locally reducing the modulation of the halftone screen, which reduces the number of possible gray levels. In the Roetling method, local averaging is performed over the binary images and the original image. Jarvis et al. perform local averaging over the original image only.
Error diffusion or error propagation methods utilize no fixed, repeated cell of pixels. Instead, these techniques involve pixel-by-pixel gray scale control processes, in which selected gray tone pixel values are switched from black to white or from white to black. See Floyd et al., "Adaptive Algorithm for Spatial Grey Scale," Proc. SID. Vol. 17, pp. 75-77, 1976. Each time a gray tone pixel value is switched to white or black, a local error in the gray scale is generated. The error is then redistributed among local pixels to correct the image. This approach tends to increase dynamic range and provide enhanced spatial resolution, thereby suppressing aliasing. See Saghri et al., cited above. Error propagation techniques are inherently serial, with error values being determined solely on the basis of previously-processed pixel values.
Ulichney (1988), cited above, addresses various methods for implementing the error propagation technique, in order to select the approach most suitable for representing a region of uniform gray level. Optimum results are obtained when the output image has certain blue noise characteristics. This effect can be achieved by modifying the basic error propagation method with a serpentine raster and Floyd filtering with fifty percent random weights. See Floyd, cited above. When the error propagation process is executed on a serpentine raster, the cumulative error determination is limited to no more than half of the neighborhood of any point. This process reduces the apparent texture patterns that appear when the unmodified error propagation technique is used.
Although error propagation methods can provide acceptable results, the computational complexity of the method increases with the area over which the error is permitted to propagate. This complexity, combined with the inherent serial execution of the method, results in excessive processing time, even for moderate size images.
Recently proposed systems for enhancing the speed and quality of halftone image generation include adaptive coding, progressive coding, and parallel processing. Adaptive coding systems assign additional gray levels are to areas of an image having low spatial frequency content, while assigning fewer gray levels to areas of high spatial frequency. An example is discussed in Carlson et al., "Adaptive Selection of Threshold Matrix Size for Pseudogray Rendition of Images," Optical Engineering, Vol. 24(4), pp. 655-662, July-August, 1985.
Adaptive coding is based upon differences in the number of grey levels that the human visual system can detect at each spatial frequency. These differences, and the corresponding desirability of locally varying the resolution and dynamic range of halftone images, is analyzed in Roetling, "Quality Measures in Digital Halftones", Optical Soc. of Am., Washington, D.C., Topical Meeting on Applied Vision, 1989, Technical Digest Series, Vol. 16, pp. 59-62; and Roetling, "Visual Performance and Image Coding," SPIE, Vol. 74 ("Image Processing") pg. 195 (1976).
Progressive coding systems divide each image into different classes of images at various resolutions. The various classes are progressively coded or binarized, and the binarization may be performed in parallel within each class of images, based on values of previously calculated classes. The process combines aspects of the ordered dither method and the error propagation technique, as each position threshold is determined on the basis of error values propagated from previously processed neighboring pixels. Progressive coding is analyzed in Anastassiou et al., "Progressive Half-toning of Images," Electronics Letters, Vol. 24, pp. 489-490, 1988.
The same authors propose a symmetric error diffusion neural network in which error values from all neighboring points are applied to calculate the binary value at a central point. The process is parallel and recursive in nature, and is intended to be implemented in neural net devices. See Anastassiou, et al., "Digital Image Halftoning Using Neural Networks," SPIE Visual Communications and Image Processing, Vol. 1001, pp. 1062-1068, 1988.
Conventional adaptive or progressive coding systems, however, typically do not provide sufficient processing speed for real-time halftone image generation. Moreover, the error diffusion neural network system requires a complex array of special-purpose digital processors. Such networks are expensive and not widely available.
It is accordingly an object of the invention to provide improved halftone imaging methods and apparatus that incorporate the respective advantages of the various classes of techniques discussed above.
A further object of the invention is to provide halftoning methods and apparatus enabling enhanced image rendition by printers and monitors having limited resolution--i.e., on the order of 512.times.512 pixels.
It is another object of the invention to provide such methods and apparatus that reduce or eliminate the visual artifacts introduced by conventional methods of dithered halftoning.
Another object of the invention is to provide apparatus and methods for high-speed, real-time halftone image generation.
It is a further object of the invention to provide apparatus and methods for high-speed generation of halftone images with readily available processing components.
Yet another object of the invention is to provide halftoning methods and apparatus that can be implemented in a parallel architecture with real-time processing and progressive image generation.
Other general and specific objects of the invention will in part be obvious and will in part appear hereinafter.